#ifndef MERGESORT_H
#define MERGESORT_H

#include "sortalgorithm.h"
#include <functional>  // 用于 Lambda 表达式

// MergeSort 继承自 SortAlgorithm，实现归并排序的逐步执行逻辑
class MergeSort : public SortAlgorithm {
public:
    // 构造函数：接收初始数据并准备工作区
    MergeSort(const QVector<int> &values);

    // 每次调用执行一步归并排序
    void step() override;

    // 返回排序是否完成
    bool isFinished() const override;

    // 获取当前可视化数据（带颜色）
    const QVector<SortBar>& getData() const override;

    // 获取并清空比较次数
    int getAndResetCompareCount() override;

    // 获取并清空交换次数
    int getAndResetSwapCount() override;

    // 返回复杂度信息（用于 UI 显示）
    QString getComplexityInfo() const override;

    // 设置升序或降序排序方式
    void setOrder(SortOrder order) override;

private:
    QVector<SortBar> bars;               // 主排序数组（带颜色）
    QVector<int> aux;                    // 辅助数组用于归并操作
    int stepIndex = 0;                   // 当前正在执行的 step 序号
    bool sorted = false;                 // 是否完成排序
    int compareCount = 0;                // 比较次数
    int swapCount = 0;                   // 数据复制/赋值次数（视为交换）
    SortOrder sortOrder = SortOrder::Ascending; // 排序顺序标志

    // 归并函数：将 bars[lo..mid] 与 bars[mid+1..hi] 合并
    void merge(int lo, int mid, int hi);

    // 收集排序操作步骤用（未在 step 中用递归）
    void mergeSort(int lo, int hi);

    // 所有应执行的合并步骤（收集而非递归调用）
    QVector<QPair<int, int>> steps;
};

#endif // MERGESORT_H
